package algorithms.leaning.class11;

import common.bean.TreeNode;
import common.util.MyUtil;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 所有层中最多节点的数量
 *
 * @author guichang
 * @date 2021/6/9
 */

@SuppressWarnings("all")
public class Code5_二叉树_层中最多的节点 {
    public static void main(String[] args) {
        TreeNode head = MyUtil.createTreeNode(1, 2, null, null, 3, 4, 5);
        MyUtil.print(maxNodes(head)); // 4
    }

    public static int maxNodes(TreeNode head) {
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(head);
        int level = 1; // 当前层数，从1开始
        int size = 1; // 当前层数节点数
        int max = size; // 返回的结果
        while (!queue.isEmpty()) {
            MyUtil.printf("第{}层有{}个节点", level, size);
            int next = 0; // 下一层节点数
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                    next++; // 下一层节点数+1
                }
                if (node.right != null) {
                    queue.offer(node.right);
                    next++; // 下一层节点数+1
                }
            }
            level++; // 层数+1
            size = next; // 循环下一层
            max = Math.max(max, next);
        }
        return max;
    }
}